home *** CD-ROM | disk | FTP | other *** search
/ Qoole for Quake / Qoole for Quake (USA) / Qoole for Quake (USA).bin / Tutorial / HTML / QUBE.ZIP / SRC / CSG4.C < prev    next >
Encoding:
C/C++ Source or Header  |  1996-11-05  |  9.4 KB  |  475 lines
  1. /* csg4.c */
  2.  
  3. #include "bsp5.h"
  4.  
  5. /*
  6.  
  7. NOTES
  8. -----
  9. Brushes that touch still need to be split at the cut point to make a tjunction
  10.  
  11. */
  12.  
  13. face_t    *validfaces[MAX_MAP_PLANES];
  14.  
  15.  
  16. face_t    *inside, *outside;
  17. int        brushfaces;
  18. int        csgfaces;
  19. int        csgmergefaces;
  20.  
  21. void DrawList (face_t *list)
  22. {
  23.     for ( ; list ; list=list->next)
  24.         Draw_DrawFace (list);
  25. }
  26.  
  27.  
  28. /*
  29. ==================
  30. NewFaceFromFace
  31.  
  32. Duplicates the non point information of a face, used by SplitFace and
  33. MergeFace.
  34. ==================
  35. */
  36. face_t *NewFaceFromFace (face_t *in)
  37. {
  38.     face_t    *newf;
  39.     
  40.     newf = AllocFace ();
  41.  
  42.     newf->planenum = in->planenum;
  43.     newf->texturenum = in->texturenum;    
  44.     newf->planeside = in->planeside;
  45.     newf->original = in->original;
  46.     newf->contents[0] = in->contents[0];
  47.     newf->contents[1] = in->contents[1];
  48.     
  49.     return newf;
  50. }
  51.  
  52.  
  53. /*
  54. ==================
  55. SplitFace
  56.  
  57. ==================
  58. */
  59. void SplitFace (face_t *in, plane_t *split, face_t **front, face_t **back)
  60. {
  61.     double    dists[MAXEDGES+1];
  62.     int        sides[MAXEDGES+1];
  63.     int        counts[3];
  64.     double    dot;
  65.     int        i, j;
  66.     face_t    *newf, *new2;
  67.     double    *p1, *p2;
  68.     vec3_t    mid;
  69.     
  70.     if (in->numpoints < 0)
  71.         Error ("SplitFace: freed face");
  72.     counts[0] = counts[1] = counts[2] = 0;
  73.  
  74. /* determine sides for each point */
  75.     for (i=0 ; i<in->numpoints ; i++)
  76.     {
  77.         dot = DotProduct (in->pts[i], split->normal);
  78.         dot -= split->dist;
  79.         dists[i] = dot;
  80.         if (dot > ON_EPSILON)
  81.             sides[i] = SIDE_FRONT;
  82.         else if (dot < -ON_EPSILON)
  83.             sides[i] = SIDE_BACK;
  84.         else
  85.             sides[i] = SIDE_ON;
  86.         counts[sides[i]]++;
  87.     }
  88.     sides[i] = sides[0];
  89.     dists[i] = dists[0];
  90.     
  91.     if (!counts[0])
  92.     {
  93.         *front = NULL;
  94.         *back = in;
  95.         return;
  96.     }
  97.     if (!counts[1])
  98.     {
  99.         *front = in;
  100.         *back = NULL;
  101.         return;
  102.     }
  103.     
  104.     *back = newf = NewFaceFromFace (in);
  105.     *front = new2 = NewFaceFromFace (in);
  106.     
  107. /* distribute the points and generate splits */
  108.  
  109.     for (i=0 ; i<in->numpoints ; i++)
  110.     {
  111.         if (newf->numpoints > MAXEDGES || new2->numpoints > MAXEDGES)
  112.             Error ("SplitFace: numpoints > MAXEDGES");
  113.  
  114.         p1 = in->pts[i];
  115.         
  116.         if (sides[i] == SIDE_ON)
  117.         {
  118.             VectorCopy (p1, newf->pts[newf->numpoints]);
  119.             newf->numpoints++;
  120.             VectorCopy (p1, new2->pts[new2->numpoints]);
  121.             new2->numpoints++;
  122.             continue;
  123.         }
  124.     
  125.         if (sides[i] == SIDE_FRONT)
  126.         {
  127.             VectorCopy (p1, new2->pts[new2->numpoints]);
  128.             new2->numpoints++;
  129.         }
  130.         else
  131.         {
  132.             VectorCopy (p1, newf->pts[newf->numpoints]);
  133.             newf->numpoints++;
  134.         }
  135.         
  136.         if (sides[i+1] == SIDE_ON || sides[i+1] == sides[i])
  137.             continue;
  138.             
  139.     /* generate a split point */
  140.         p2 = in->pts[(i+1)%in->numpoints];
  141.         
  142.         dot = dists[i] / (dists[i]-dists[i+1]);
  143.         for (j=0 ; j<3 ; j++)
  144.         {    /* avoid round off error when possible */
  145.             if (split->normal[j] == 1)
  146.                 mid[j] = split->dist;
  147.             else if (split->normal[j] == -1)
  148.                 mid[j] = -split->dist;
  149.             else
  150.                 mid[j] = p1[j] + dot*(p2[j]-p1[j]);
  151.         }
  152.     
  153.         VectorCopy (mid, newf->pts[newf->numpoints]);
  154.         newf->numpoints++;
  155.         VectorCopy (mid, new2->pts[new2->numpoints]);
  156.         new2->numpoints++;
  157.     }
  158.  
  159.     if (newf->numpoints > MAXEDGES || new2->numpoints > MAXEDGES)
  160.         Error ("SplitFace: numpoints > MAXEDGES");
  161.  
  162. #if 0    
  163. CheckFace (newf);
  164. CheckFace (new2);
  165. #endif
  166.  
  167. /* free the original face now that is is represented by the fragments */
  168.     FreeFace (in);
  169. }
  170.  
  171. /*
  172. =================
  173. ClipInside
  174.  
  175. Clips all of the faces in the inside list, possibly moving them to the
  176. outside list or spliting it into a piece in each list.
  177.  
  178. Faces exactly on the plane will stay inside unless overdrawn by later brush
  179.  
  180. frontside is the side of the plane that holds the outside list
  181. =================
  182. */
  183. void ClipInside (int splitplane, int frontside, qboolean precedence)
  184. {
  185.     face_t    *f, *next;
  186.     face_t    *frags[2];
  187.     face_t    *insidelist;
  188.     plane_t *split;
  189.     
  190.     split = &planes[splitplane];
  191.     
  192.     insidelist = NULL;
  193.     for (f=inside ; f ; f=next)
  194.     {
  195.         next = f->next;
  196.         
  197.         if (f->planenum == splitplane)
  198.         {    /* exactly on, handle special */
  199.             if ( frontside != f->planeside || precedence )
  200.             {    /* allways clip off opposite faceing */
  201.                 frags[frontside] = NULL;
  202.                 frags[!frontside] = f;
  203.             }
  204.             else
  205.             {    /* leave it on the outside */
  206.                 frags[frontside] = f;
  207.                 frags[!frontside] = NULL;
  208.             }
  209.         }
  210.         else
  211.         {    /* proper split */
  212.             SplitFace (f, split, &frags[0], &frags[1]);
  213.         }
  214.         
  215.         if (frags[frontside])
  216.         {
  217.             frags[frontside]->next = outside;
  218.             outside = frags[frontside];
  219.         }
  220.         if (frags[!frontside])
  221.         {
  222.             frags[!frontside]->next = insidelist;
  223.             insidelist = frags[!frontside];
  224.         }
  225.     }
  226.     
  227.     inside = insidelist;
  228. }
  229.  
  230.  
  231. /*
  232. ==================
  233. SaveOutside
  234.  
  235. Saves all of the faces in the outside list to the bsp plane list
  236. ==================
  237. */
  238. void SaveOutside (qboolean mirror)
  239. {
  240.     face_t    *f , *next, *newf;
  241.     int        i;
  242.     int        planenum;
  243.         
  244.     for (f=outside ; f ; f=next)
  245.     {
  246.         next = f->next;
  247.         csgfaces++;
  248.         Draw_DrawFace (f);
  249.         planenum = f->planenum;
  250.         
  251.         if (mirror)
  252.         {
  253.             newf = NewFaceFromFace (f);
  254.             
  255.             newf->numpoints = f->numpoints;
  256.             newf->planeside = f->planeside ^ 1;    /* reverse side */
  257.             newf->contents[0] = f->contents[1];
  258.             newf->contents[1] = f->contents[0];
  259.     
  260.             for (i=0 ; i<f->numpoints ; i++)    /* add points backwards */
  261.             {
  262.                 VectorCopy (f->pts[f->numpoints-1-i], newf->pts[i]);
  263.             }
  264.         }
  265.         else
  266.             newf = NULL;
  267.  
  268.         validfaces[planenum] = MergeFaceToList(f, validfaces[planenum]);
  269.         if (newf)
  270.             validfaces[planenum] = MergeFaceToList(newf, validfaces[planenum]);
  271.  
  272.         validfaces[planenum] = FreeMergeListScraps (validfaces[planenum]);
  273.     }
  274. }
  275.  
  276. /*
  277. ==================
  278. FreeInside
  279.  
  280. Free all the faces that got clipped out
  281. ==================
  282. */
  283. void FreeInside (int contents)
  284. {
  285.     face_t    *f, *next;
  286.     
  287.     for (f=inside ; f ; f=next)
  288.     {
  289.         next = f->next;
  290.         
  291.         if (contents != CONTENTS_SOLID)
  292.         {
  293.             f->contents[0] = contents;
  294.             f->next = outside;
  295.             outside = f;
  296.         }
  297.         else
  298.             FreeFace (f);
  299.     }
  300. }
  301.  
  302.  
  303. /*========================================================================== */
  304.  
  305. /*
  306. ==================
  307. BuildSurfaces
  308.  
  309. Returns a chain of all the external surfaces with one or more visible
  310. faces.
  311. ==================
  312. */
  313. surface_t *BuildSurfaces (void)
  314. {
  315.     face_t            **f;
  316.     face_t            *count;
  317.     int                i;
  318.     surface_t        *s;
  319.     surface_t        *surfhead;
  320.     
  321.     surfhead = NULL;
  322.     
  323.     f = validfaces;
  324.     for (i=0 ; i<numbrushplanes ; i++, f++)
  325.     {
  326.         if (!*f)
  327.             continue;    /* nothing left on this plane */
  328.  
  329. /* create a new surface to hold the faces on this plane */
  330.         s = AllocSurface ();
  331.         s->planenum = i;
  332.         s->next = surfhead;
  333.         surfhead = s;
  334.         s->faces = *f;
  335.         for (count = s->faces ; count ; count=count->next)
  336.             csgmergefaces++;
  337.         CalcSurfaceInfo (s);    /* bounding box and flags */
  338.     }    
  339.     
  340.     return surfhead;
  341. }
  342.  
  343. /*========================================================================== */
  344.  
  345. /*
  346. ==================
  347. CopyFacesToOutside
  348. ==================
  349. */
  350. void CopyFacesToOutside (brush_t *b)
  351. {
  352.     face_t        *f, *newf;
  353.     
  354.     outside = NULL;
  355.     
  356.     for (f=b->faces ; f ; f=f->next)
  357.     {
  358.         brushfaces++;
  359. #if 0
  360. {
  361.     int        i;
  362.     
  363.     for (i=0 ; i<f->numpoints ; i++)
  364.         ShowTempEntry("(%f,%f,%f) ",f->pts[i][0], f->pts[i][1], f->pts[i][2]);
  365. }
  366. #endif
  367.         newf = AllocFace ();
  368.         *newf = *f;
  369.         newf->next = outside;
  370.         newf->contents[0] = CONTENTS_EMPTY;
  371.         newf->contents[1] = b->contents;
  372.         outside = newf;
  373.     }
  374. }
  375.  
  376.  
  377. /*
  378. ==================
  379. CSGFaces
  380.  
  381. Returns a list of surfaces containing all of the faces
  382. ==================
  383. */
  384. surface_t *CSGFaces (brushset_t *bs)
  385. {
  386.     brush_t        *b1, *b2;
  387.     int            i;
  388.     qboolean        overwrite;
  389.     face_t        *f;
  390.     surface_t    *surfhead;
  391.     int        total, cur;
  392.  
  393.     ShowStatusEntry("Merging faces with CSG.");
  394.  
  395.     /* Perform a relatively quick (O(n)) scan to count faces */
  396.     for (total = 0, b1=bs->brushes ; b1 ; b1 = b1->next, total++) ;
  397.  
  398.     ShowTempEntry("%5d faces to merge.", total);
  399.  
  400.     memset (validfaces, 0, sizeof(validfaces));
  401.     
  402.     csgfaces = brushfaces = csgmergefaces = 0;
  403.     
  404.     Draw_ClearWindow ();
  405.     
  406. /* */
  407. /* do the solid faces */
  408. /* */
  409.     ShowTempEntry("Setup complete; starting merge job.");
  410.  
  411.         for (cur = 0, b1=bs->brushes ; b1 ; b1 = b1->next, cur++)
  412.     {
  413.         PercentBar(cur * 256 / total);
  414.     /* set outside to a copy of the brush's faces */
  415.         CopyFacesToOutside (b1);
  416.         
  417.         overwrite = false;
  418.         
  419.         for (b2=bs->brushes ; b2 ; b2 = b2->next)
  420.         {
  421.         /* see if b2 needs to clip a chunk out of b1 */
  422.         
  423.             if (b1==b2)
  424.             {
  425.                 overwrite = true;    /* later brushes now overwrite */
  426.                 continue;
  427.             }
  428.  
  429.         /* check bounding box first */
  430.             for (i=0 ; i<3 ; i++)
  431.                 if (b1->mins[i] > b2->maxs[i] || b1->maxs[i] < b2->mins[i])
  432.                     break;
  433.             if (i<3)
  434.                 continue;
  435.  
  436.         /* divide faces by the planes of the new brush */
  437.         
  438.             inside = outside;
  439.             outside = NULL;
  440.             
  441.             for (f=b2->faces ; f ; f=f->next)
  442.                 ClipInside (f->planenum, f->planeside, overwrite);
  443.  
  444.         /* these faces are continued in another brush, so get rid of them */
  445.             if (b1->contents == CONTENTS_SOLID && b2->contents <= CONTENTS_WATER)
  446.                 FreeInside (b2->contents);
  447.             else
  448.                 FreeInside (CONTENTS_SOLID);
  449.         }
  450.         
  451.     /* all of the faces left in outside are real surface faces */
  452.         if (b1->contents != CONTENTS_SOLID)
  453.             SaveOutside (true);    /* mirror faces for inside view */
  454.         else
  455.             SaveOutside (false);
  456.     }
  457.  
  458. #if 0
  459.     if (!csgfaces)
  460.         Error ("No faces");
  461. #endif
  462.  
  463.     surfhead = BuildSurfaces ();
  464.     
  465.     ShowTempEntry("%5i Brush faces.", brushfaces);
  466.     ShowTempEntry("%5i CSG faces.", csgfaces);
  467.     ShowTempEntry("%5i Merged faces.", csgmergefaces);
  468.  
  469.     PercentBar(0);
  470.         
  471.     return surfhead;
  472. }
  473.  
  474.  
  475.